package interview.data_structure;

import common.Util;

/**
 * @author fance
 * @date 2018/7/12 10:37
 */
public class MaxPQ {

    private Integer[] pq;
    private int N = 0;

    public MaxPQ(int maxN) {
        pq = new Integer[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    private void exch(int i, int j) {
        int t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }


    private void swim(int k) {
        while (k > 1 && less(k / 2,k)) {
            exch(k/ 2, k);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j,j + 1)) {
                j++;
            }
            if (!less(k,j)) {
                break;
            }
            exch(k,j);
            k = j;
        }
    }

    public void insert(int v) {
        pq[++N] = v;
        swim(N);
    }

    public int delMax() {
        int max = pq[1];
        exch(1,N--);
        pq[N + 1] = null;
        sink(1);
        return max;
    }


    int leftChild(int i) {
        return 2 * i + 1;
    }
    void sink(int[] a,int i,int n) {
        int child;
        int tmp = a[i];
        for (; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child + 1] > a[child]) {
                child++;
            }

            if (tmp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;
    }

    public void heapSort(int[] a,int n) {
        for (int i = n / 2; i >= 0; i--) {
            // buildHeap
            sink(a,i,n);
        }

        for (int i = n - 1; i > 0; i--) {
            Util.swap(a,0,i);
            sink(a,0,i);
        }
    }
}
